% TODO Историческое введение
% TODO Теория множеств Гёделя-Бернайса

\begin{definition}
\textit{Предкатегория} (\textit{Диаграмма}) --- четвёрка $(C_1,C_0,o,t)$, где
\index{Предкатегория}\index{Диаграмма}

  $C_1$ --- класс стрелок (морфизмов)

  $C_0$ --- класс вершин (объектов)
  
  $o,t\colon C_1\to C_0$
\end{definition}

$o(\alpha)$ --- начало (источник) $\alpha$

$t(\alpha)$ --- конец (цель) $\alpha$

Запись $x\stackrel{\alpha}{\longrightarrow} y$ означает $o(\alpha)=x$ и $t(\alpha)=y$

\begin{definition}
\textit{Категория} --- объект $(C_1,C_0,o,t,I,\circ)$, где \index{Категория}

$(C_1,C_0,o,t)$ --- предкатегория

$I\colon C_0\to C_1$

$C_2\leftrightharpoons \{(\alpha,\beta)\in C_1\times C_1\mid t(\alpha)=o(\beta)\}$

$I\colon C_0\to C_1$

$\circ\colon C_2\to C_1$

Запись $\alpha\circ \beta$ означает композицию $\alpha$ и $\beta$. \index{Композиция}
Запись $I(x)=\mathrm{id}_x=1_x$~--- тождественную стрелку. \index{Тождественная стрелка}

Чтобы эта шестёрка была категорией, должны быть выполнены аксиомы:
\begin{enumerate}
  \item $I(x): x\to x$ (т.е. $o(I(x))=x$, $t(I(x))=x$ для всех $x\in C_0$)
  \item $x\stackrel{\alpha}{\longrightarrow} y\stackrel{\beta}{\longrightarrow} z \Longrightarrow x\stackrel{\alpha\circ\beta}{\longrightarrow} z$
  \item $x\stackrel{\alpha}{\longrightarrow}
         y\stackrel{\beta}{\longrightarrow}
         z\stackrel{\gamma}{\longrightarrow} w \Longrightarrow 
         (\alpha\circ\beta)\circ\gamma=\alpha\circ(\beta\circ\gamma)$
  \item $x\stackrel{\alpha}{\longrightarrow} y \Longrightarrow
         1_x\circ\alpha=\alpha\circ 1_y=\alpha$
\end{enumerate}

Если $C$ --- категория, то введём обозначения
$$\mathrm{Mor}C \leftrightharpoons C_1, \mathrm{Ob}C \leftrightharpoons C_0$$
$$C(x,y)\leftrightharpoons \{\alpha\in \mathrm{Mor}C\mid x\stackrel{\alpha}{\longrightarrow} y\}$$
$$\mathrm{Hom}(x,y)\leftrightharpoons C(x,y)$$
\end{definition}

\begin{definition}
Категория $C$ называется \textit{малой}, если $\mathrm{Mor}C$ --- множество.\index{Категория малая}
\end{definition}

%\subsection{Примеры категорий}

\begin{category}
  Пустая.
\end{category}

\begin{category}
  $\mathrm{SET}$ (категория множеств) \index{SET}
  
  $SET(x,y) \leftrightharpoons$ множество всех функций $x\to y$ (обозначается $y^x$)

  $1_x\colon x\to x$ --- тождественная функция множества в себя
\end{category}

\begin{definition}
  $C$ является \textit{подкатегорией} $D$ (обозначение: $C\subseteq D$),
  если \index{Подгатегория}
  \begin{enumerate}
    \item $\mathrm{Ob}C\subseteq \mathrm{Ob}D$
    \item $\mathrm{Mor}C\subseteq \mathrm{Mor}D$
    \item $C(x,y)\subseteq D(x,y)$ для всех $x,y\in\mathrm{Ob}C$
    \item $I_C(x)=I_D(x)$, если $x\in \mathrm{Ob}C$
    \item $\alpha\circ_C \beta = \alpha\circ_D \beta$, если $\alpha,\beta\in \mathrm{Mor}_C$
  \end{enumerate}
\end{definition}

\begin{category}
  $\mathrm{FINSET}$ (категория конечных множеств) \index{FINSET}
  
  Она является подкатегорией категории $\mathrm{SET}$, т.е. $\mathrm{FINSET}\subseteq \mathrm{SET}$
\end{category}

\begin{definition}
  Если $C$ --- категория, то можно ввести \textit{двойственную}\index{Категория двойственная}
  категорию (обозначение: $C^{\circ}$)

  $\mathrm{Ob}C^{\circ}\leftrightharpoons \mathrm{Ob}C$

  $\mathrm{Mor}C^{\circ}\leftrightharpoons \mathrm{Mor}C$

  $C^{\circ}(x,y)\leftrightharpoons C(x,y)$

  $\alpha\circ_{C^{\circ}}\beta\leftrightharpoons \beta\circ_C \alpha$, если
  $\alpha,\beta\in \mathrm{Mor}C$
\end{definition}

\begin{exercise}
  Доказать, что $C^{\circ}$ --- это действительно категория.
\end{exercise}

\begin{category}
  $\mathrm{SET}^{\circ}$ --- категория, двойственная категории множеств.
\end{category}

\begin{definition}
  $\alpha$ называется \textit{изострелкой}\index{Изострелка} (или
  \textit{изоморфизмом}\index{Изоморфизм}),
  если \\
  $x\stackrel{\alpha}{\longrightarrow} y$
  и $\exists\beta: y\to x$ такая, что:
    $$\left\{
        \begin{aligned}
          \alpha\circ\beta=1_x\\
          \beta\circ\alpha=1_y\\
        \end{aligned}
      \right.
    $$

  Изострелки будем обозначать так: $x\xrightarrow[\sim]{\alpha} y$.
  % TODO надпись под стрелкой
\end{definition}

\begin{exercise}
  Изострелки в $C^{\circ}$ те же, что и в $C$.
\end{exercise}

\begin{definition}
  Будем говорить, что $x$ \textit{изоморфно}\index{Изоморфно} $y$,
  и писать $x\approx_C y$, если в категории $C$ 
  существует изострелка $\alpha:~x\to~y$.
\end{definition}

\begin{lemma}
  Стрелки $\beta,\gamma$ обратны к $\alpha \Rightarrow \beta=\gamma$.
\end{lemma}

\begin{proof}
  $\gamma=
   (\beta\circ\alpha)\circ\gamma=
   \beta\circ(\alpha\circ\gamma)=
   \beta$
\end{proof}

\begin{definition}
  Если у $\alpha$ существует обратный, то будем его обозначать $\alpha^{-1}$.
\end{definition}

\begin{lemma} (1) Пусть $x\stackrel{\alpha}{\longrightarrow} y$ и
     $y\stackrel{\beta}{\longrightarrow} z$ --- изострелки. Тогда $\alpha\circ\beta$ --- изострелка и $(\alpha\circ\beta)^{-1}=\beta^{-1}\circ\alpha^{-1}$

(2) $\approx_C$ задаёт отношение эквивалентности на множестве объектов.
\end{lemma}

\begin{proof}
  (1) $(\alpha\circ\beta)\circ(\beta^{-1}\circ\alpha^{-1})=
       \alpha\circ((\beta\circ\beta^{-1})\circ\alpha^{-1})=1_x$

     Аналогично в обратном порядке. По определению, получаем
     $(\alpha\circ\beta)^{-1}=\beta^{-1}\circ\alpha^{-1}$.

  (2) Проверяем свойства эквивалентности:
    \begin{enumerate}
      \item $1_x\circ1_x=1_x \Rightarrow x\approx_C x$\\
      \item $x\stackrel{\alpha}{\longrightarrow} y$ и
            $y\stackrel{\beta}{\longrightarrow} z$ --- изострелки
            $ \Rightarrow
            x\stackrel{\alpha\circ\beta}{\longrightarrow} z$,
            т.е. $\approx_C$ транзитивно.\\
      \item Если $x\stackrel{\alpha}{\longrightarrow} y$ --- изострелка,
            то $y\stackrel{\alpha^{-1}}{\longrightarrow} x$ --- тоже изострелка,
            поэтому~$\approx_C$ симметрично.\\
    \end{enumerate}
\end{proof}

\begin{definition}
  $x$ --- \textit{начальный объект}\index{Начальный объект}
          (или \textit{левый нуль}\index{Левый нуль})
          в категории $C$, если $\forall y\in\mathrm{Ob}C\; |C(x,y)|=1$.
\end{definition}

\begin{definition}
  $x$ --- \textit{финальный объект}\index{Финальный объект}
          (или \textit{правый нуль}\index{Правый нуль})
          в категории $C$, если $\forall y\in\mathrm{Ob}C\; |C(y,x)|=1$.
\end{definition}

\begin{lemma}
  (1) Все начальные объекты изоморфны. % TODO: что такое изоморфны?

  (2) Все финальные объекты изоморфны.
\end{lemma}

\begin{proof}
  Пусть $x$ и $y$ --- два начальных (финальных) объекта. Тогда $|C(x,y)|=1$ и
  $|C(y,x)|=1$, поэтому существуют стрелки
  $x\stackrel{\alpha}{\longrightarrow}y$ и $y\stackrel{\beta}{\longrightarrow}x$,
  причём $x\stackrel{\alpha\circ \beta}{\longrightarrow}x$. Заметим, что
  $|C(x,x)|=1$, поэтому $\alpha\circ \beta=1_x$. Аналогично, $\beta\circ\alpha=1_y$.
  Следовательно, $x\approx_C y$
\end{proof}
